package com.hyb.algorithm.data.struct.backtrack;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 39. 组合总和
 * https://leetcode.cn/problems/combination-sum/description/
 *
 * @author: ybhu
 * @create: 2023/12/29 08:12
 */
public class CombinationSum {

    public static void main(String[] args) {

        int[] candidates = new int[]{2, 3, 6, 7};
        List<List<Integer>> res = new CombinationSum().combinationSum(candidates, 7);


        System.out.println(JSONObject.toJSON(res));

    }


    private List<List<Integer>> res;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        res = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();

        backTrack(candidates, target, 0, list);

        return res;
    }


    public void backTrack(int[] candidates, int target, int start, List<Integer> list) {

        if (start >= candidates.length) {
            return;
        }

        if (target < 0) {
            return;
        }

        if (0 == target) {
            res.add(new ArrayList(list));
            return;
        }

        //直接跳过该元素  start增加1 target不变
        backTrack(candidates, target, start + 1, list);

        //选择该元素， start继续保持原来的  target 减去当前选择的值
        if (target - candidates[start] >= 0) {
            list.add(candidates[start]);
            backTrack(candidates, target - candidates[start], start, list);
            //回溯
            list.remove(list.size() - 1);
        }
    }
}

